#include <stdio.h>
#include <stdlib.h>
//338. 比特位计数
//给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

// 1.方法一：
// 由十进制和二进制的转换可知，当该数字模上2的结果为1时，其二进制就显示一个1，依据此特点，判断二进制位上是否为1，计算出个数。
// 2.方法二：
// 任何数字与1进行按位与操作，只有其个位为1时得到结果才会为真，利用这一点
// 将这个数字的二进制与0x01进行按位与，然后将其二进制右移一位重复此操作，得到最终结果。
//3.方法三：
// 一个数字与上这个数字减一的数，该数二进制最右边的1必然会消除掉，以此类推，从右往左，每一次进行按位与操作，都会取消掉一个1，
//直到该数字变为0，跳出循环，就得到了该数字二进制中1的个数。


int* countBits(int n, int* returnSize) 
{
    *returnSize = n+1;
    int *ret = malloc(sizeof(int *) *(n+1));
    for(int i = 0; i <= n; i++)
    {
        int count = 0;
        int num = i;
        if(num == 0)
        {
            ret[i] = 0;
            continue;
        }
        while(num)
        {
            num = num & (num-1);
            count++;
        }   
        ret[i] = count;                                     
    }
    return ret;
}

